#include "main/utils.h"
using namespace std;

struct TrieNode {
  bool terminal = 0;
  TrieNode* childern[26];
};

class Trie {
  public:
    Trie() {
      root = new TrieNode();
    };

    void insert(string str) {
      auto node = root;
      for (auto ele : str) {
        if (node->childern[ele - 'a'] == nullptr)
          node->childern[ele - 'a'] = new TrieNode();
        node = node->childern[ele - 'a'];
      }
      node->terminal = true;
    }

    bool search(string str) {
      auto node = root;
      for (auto ele : str) {
        if (node->childern[ele - 'a'] == nullptr) {
          return false;
        }
        node = node->childern[ele - 'a'];
      }
      return node->terminal;
    }

    bool startWith(string str) {
      auto node = root;
      for (auto ele : str) {
        if (node->childern[ele - 'a'] == nullptr) {
          return false;
        }
        node = node->childern[ele - 'a'];
      }
      return true;
    }

  private:
    TrieNode* root;
};

int main() {
  Trie trie;
  trie.insert("goodbye");
  trie.insert("boy");
  trie.insert("boss");
  trie.insert("cowboy");
  trie.insert("cow");

  cout << trie.search("good") << " 0" << endl;
  cout << trie.search("goodbye") << " 1" << endl;
  cout << trie.search("boy") << " 1" << endl;
  cout << trie.search("cowboy") << " 1" << endl;
  cout << trie.search("cow") << " 1" << endl;
  cout << trie.search("coy") << " 0" << endl;

  cout << trie.startWith("good") << " 1" << endl;
  cout << trie.startWith("cow") << " 1" << endl;
  cout << trie.startWith("bo") << " 1" << endl;
  cout << trie.startWith("a") << " 0" << endl;

  return 0;
}
